package 字符串.字符串排序;

import java.util.Arrays;

/**
 * @description:
 * @author: ywk
 * @date: 2021-08-31
 */
public class 三向字符串快速排序 {
    public static void main(String[] args) {
        String[] arr = new String[]{"abv", "abc", "cba", "cvc", "bca", "cda"};
        Quick3String quick3String = new Quick3String();
        quick3String.sort(arr);
        System.out.println(Arrays.asList(arr));
    }

    public  static class Quick3String {
        private static int charAt(String s, int d) {
            if (d < s.length()) {
                return s.charAt(d);
            }
            return -1;
        }

        public  static void sort(String[] a) {
            sort(a, 0, a.length - 1, 0);
        }

        private static void sort(String[] a, int lo, int hi, int d) {
            if (hi <= lo) {
                return;
            }
            int lt = lo, gt = hi;
            int v = charAt(a[lo], d);
            int i = lo + 1;
            while (i <= gt) {
                int t = charAt(a[i], d);
                if (t < v) {
                    exch(a, lt++, i++);
                } else if (t > v) {
                    exch(a, i, gt--);
                }else{
                    i++;
                }

            }
            sort(a, lo, lt - 1, d);
            if (v >= 0) {
                sort(a, lt, gt, d + 1);
            }
            sort(a, gt + 1, hi, d);
        }

        private static void exch(String[] a, int i, int j) {
            String tem = a[i];
            a[i] = a[j];
            a[j] = tem;
        }
    }
}
